Потокові алгоритми

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКНІ
Факультет:
Комп’ютерні науки
Кафедра:
Кафедра САПР

Інформація про роботу

Рік:
2015
Тип роботи:
Лабораторна робота
Предмет:
Дискретні моделі в САПР

Частина тексту файла

НУЛП, ІКНІ, САПР Тема оцінка підпис    Потокові алгоритми         № залікової:     Дискретні моделі в САПР  Викладач:       Мета роботи : метою даної лабораторної роботи є вивчення потокових алгоритмів. Короткі теоретичні відомості : Останнім часом значно зросла зацікавленість учених та практиків потоковими моделями. Це пов’язано із впровадженням та активним розвитком різноманітних територіально розподілених систем: трубопровідних, транспортних, телекомунікаційних та ін. Основою таких систем є певна мережа (мережа трубопроводів, доріг, каналів зв’язку тощо), в якій циркулюють певні потоки (потоки речовин, транспорту, даних тощо), тому задачі, які доводиться розв’язувати при проектуванні та експлуатації систем з мережною структурою, часто зводяться до розробки математичних моделей розподілу потоків та постановки і розв’язання відповідних оптимізаційних задач. Відомі моделі розподілу потоків у мережах базуються на поняттях теорії графів. Це пов’язано з тим, що граф дає можливість наочно відобразити структуру мережі, а параметри його вузлів і дуг – представити основними числовими характеристиками її елементів. Набір характеристик залежить від природи модельованої системи, а також характеру розв’язуваних задач, однак у потокових моделях їх, як правило, представляють такими параметрами, як зовнішній потік у вузлі, потік по дузі, пропускна здатність дуги, вартість передавання одиниці потоку по дузі тощо. Потокові задачі, як правило, зводяться до пошуку такого розподілу потоків у мережі, при якому б забезпечувався екстремум деякого критерію. При цьому мають враховуватися обмеження, що накладаються умовами збереження потоків у вузлах і неперевищення потоками пропускної здатності дуг. Типовими потоковими задачами є задача про потік мінімальної вартості, про максимальний потік, транспортна задача, задача про призначення та інші. Для їх розв’язання розроблено чимало ефективних алгоритмів, сформувався навіть відповідний напрям обчислювальних методів під назвою потокового програмування. Потік-визначає спосіб пересилання деяких об’єктів з одного пункту в інший. Розв’язання задачі потоку зводиться до таких основних підзадач: максимізація сумарного обсягу перевезень; мінімізація вартості пересилань предметів з одного пункту в інший; мінімізація часу перевезень в заданій системі. Реалізація алгоритму (Java) : int maxFlow = 0;//Початковий максимальний потік int pathFlow;//Тимчасовий потік int[][] residualGraph = new int[numberOfVertices + 1][numberOfVertices + 1];//Залишкова матриця ваг графу /* Копіювання матриці ваг в залишуову матрицю */ for (int sourceVertex = 1; sourceVertex <= numberOfVertices; sourceVertex++) { for (int destinationVertex = 1; destinationVertex <= numberOfVertices; destinationVertex++) { residualGraph[sourceVertex][destinationVertex] = graph[sourceVertex][destinationVertex]; } } /* Доки шлях існує знаходимо найкращий потік */ while (bfs(source ,destination, residualGraph)) { pathFlow = Integer.MAX_VALUE; for (v = destination; v != source; v = parent[v]) { u = parent[v]; pathFlow = Math.min(pathFlow, residualGraph[u][v]); } for (v = destination; v != source; v = parent[v]) { u = parent[v]; residualGraph[u][v] -= pathFlow; residualGraph[v][u] += pathFlow; System.out.println(v + " до " + u); } System.out.println(pathFlow); maxFlow += pathFlow; } return maxFlow; } Інструкція по експлуатації: Для роботи програми необхідно запустити файл Lab_3_DM.java . Спочатку необхідно ввести кількість вершин графа, далі матрицю ваг, початкову та кінцеву точки потоку. Далі програма знаходить максимальний потік та виводить його значення. Граф: Результат виконання: ***HELP*** 0. Програма знаходить максимальний потік в графі! Для коректної роботи програми необ...
Антиботан аватар за замовчуванням
JB

13.05.2016 23:05

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини